Masala #0327

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 34 %
14

  

Eng kuchlilar musobaqasi

Robolandiya mamlakatida sport dasturchilari orasida final musobaqasi bo’lib o’tmoqda. Bu final musobaqasiga eng kuchlilar ishtirok etishmoqda va ularning barchasi musobaqadagi barcha masalalarni ishlash kuchiga ega, va ular shunchalik kuchli tayyorgarlik ko’rishganki, har bir ishtirokchi har bir masalani aynan 1 minutda va aynan 1 urinishda ishlab tugatadi.

Barcha ishtirokchilar shunday xususiyatga ega ekanligidan ma’lumki eng kam jarima olgan ishtirokchi g’olib bo’ladi. Buni bilgan hay’at a’zolari jarima vaqtini hisoblashning o’zgacha bir usulini ishlab chiqishdi.

Musobaqadagi jami N ta masala uchun N ta elementdan iborat A to’plamni hosil qilishdi. i-masala uchun jarima vaqti i-masala ishlangan vaqtdagi Ai qiymatga teng. Bu to’plam har minutda o’zgarib turish xususiyatiga ega. Bu o’zgarishda to’plamning i-elementi j-minut yakunida (j+1)*Ai ga ortadi, ya’ni Ai=Ai+ (j+1)*Ai ga o’zgaradi.

Hay’at a’zolarining bunday qarorlarini bilmagan holda Bitboy musobaqadagi barcha masalani ishlagan holda olinishi mumkin bo’lgan eng kichik jarima vaqtini bilan 1-o’rinni egalladi. Sizning vazifangiz Bitboyning musobaqadagi jarima vaqtini hisoblashdan iborat.


Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 10), testlar soni kiritiladi.

Har bir testing dastlabki satrida bitta butun son, N(1 ≤ N ≤ 105) musobaqadagi masalalar soni, hamda ikkinchi satrida N ta butun son, hay’at a’zolari hosil qilgan A(1 ≤ Ai ≤ 109) to’plam elementlari kiritiladi.


Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda bitta butun son, Bitboyning musobaqadagi jarima vaqtini 109+7 ga bo’lgandagi qoldiqni chop eting.


Misollar
# input.txt output.txt
1
1
2
3 3
9
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin